class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

    class Partition {
        public ListNode partition(ListNode head, int x) {
            //拦截异常
            if (head == null) {
                return null;
            }
            if (head.next == null) {
                return head;
            }
            // write code here
            //头节点
            ListNode front = new ListNode(-1);
            ListNode recordFront = front;
            ListNode back = new ListNode(-1);
            ListNode record = back;
            while (head != null) {
                //提前保存下一个节点
                ListNode nextNode = head.next;
                //尾插到两个链表中
                if (head.val < x) {
                    front.next = head;
                    front = front.next;
                } else {
                    back.next = head;
                    back = back.next;
                }
                head = nextNode;
            }
            front.next = record.next;
            return recordFront.next;
        }


    }
public class Main{
    public static void main(String[] args) {
        Partition test = new Partition();
    }

}
